/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function(n) {
    if(n<=2) return n
    let dp=new Array(n+1).fill(Infinity)
    //初始化一些方便算的状态
    dp[0]=0
    dp[1]=1
    dp[2]=2
    //dp[n]表示 和为n的完全平方数的数量
    // 对于某个dp[n] 他某一个dp[j]+一个完全方数得来的
    // 这个完全平方数的范围是多少？由于n不可能是一个大于n的完全平方数加出来的，
    // 由于完全平方数是一个数的平方，最小的完全平方数是1，由1*1得来，所以我们从最小数1开始，每次加1，看这个数的平方是不是大于 n，大于的不可能取到
    // 于是得到了完全平方数的范围，其余推导过程和硬币一样
    for(let i=3;i<=n;i++){
       let maxNum=1
       while(maxNum*maxNum<=i){
            let step=maxNum*maxNum
            dp[i]=Math.min(dp[i],dp[i-step]+1)
           maxNum++
       }
    }
    return dp[n]
};

let n=12
console.log(numSquares(n));